/*
 * https://leetcode-cn.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/
 */

typedef struct {
    int len;
    int start;
    UT_hash_handle hh;
} ut_hash_t;

ut_hash_t *map;
void hash_add_len(ut_hash_t *k)
{
    HASH_ADD_INT(map, len, k);
}
int by_len(const ut_hash_t *a, const ut_hash_t *b)
{
    return (a->len - b->len);
}
int minSumOfLengths(int* arr, int arrSize, int target){
    int left = 0, right = 0, sum = 0;
    map = NULL;
    while (right < arrSize) {
        sum += arr[right];
        right++;
        if (sum < target) continue;
        while (sum > target) {
            sum -= arr[left];
            left++;
        }
        if (sum == target) {
            ut_hash_t *k = (ut_hash_t *)malloc(sizeof(ut_hash_t));
            k->len = right - left;
            k->start = left;
            hash_add_len(k);
        }
    }
    HASH_SORT(map, by_len);
    int ret = INT_MAX;
    ut_hash_t *m1 = NULL;
    for (m1 = map; m1 != NULL; m1 = m1->hh.next) {
        if (m1->len *2 >= ret) break;
        ut_hash_t *m2 = m1;
        while ((m2 = m2->hh.next) != NULL) {
            if (m1->start < m2->start && m1->start + m1->len > m2->start) continue;
            if (m2->start < m1->start && m2->start + m2->len > m1->start) continue;
            ret = (ret < m1->len + m2->len) ? ret : (m1->len + m2->len);
            break;
        }
    }
    return ret == INT_MAX ? -1 : ret;
}